1. Field of the Invention
This invention relates in general to a method for collating bits from a source of bytes. More particularly, it is directed to an efficient method of collating bit subchannels from a buffer holding a number of bytes or a stream of bytes or other sources of bytes.
2. Description of Related Art
In communication systems, it is often the case that upon transmission of data, for example a stream of bytes, the data loses its byte boundaries such that the receiver receives the stream of bytes in some randomly rotated order. In such cases, the data must be reoriented by the receiver before it may be used. The process of reorienting the data typically involves searches by the receiver for a predesignated bit-pattern in the stream of bytes received.
Often times the search for the predesignated bit-pattern requires examination of the bits in the stream of bytes that share a common bit position in their respective bytes. For example, in the area of video signal processing, frame structures containing information such as audio and video data, are transmitted over transmission channels. In accordance with the ITU-T Recommendation H.221, the information to be transmitted is arranged in a frame structure, a typical example of which is shown in FIG. 1 as frame structure 10. As shown in FIG. 1, the frame structure 10 is made up of a stack of 80 bytes of data, each byte consisting of 8 bits. Each column of bits in the frame structure 10 is referred to as a subchannel 20. These subchannels are grouped into what is referred to as a "channel". Each channel contains a specific type of data, and each may have a different number of subchannels. For example, the frame in FIG. 1 comprises three channels, an audio channel 30, a video channel 40 and the service channel 50. The audio channel 30 carries audio data and comprising two subchannels. The video channel 40 carries video data and comprises five subchannels at top of the frame and six subchannels at bottom of the frame. The service channel 50 comprises a segment of one subchannel, and its function is described below.
The ITU-T Recommendation H.221 specifies that a particular frame bit-pattern must occupy the service channel 50. Among other functions, this pattern allows the system receiving the stream of bytes to locate the start of the frame structure and to discover by how many bit positions the bytes have been rotated in the communications channel.
The frame structures are transmitted over the ISDN communication channels continuously in a stream of bytes. As mentioned earlier, during the transmission, the byte boundaries are often lost such that the receiver receives a randomly rotated stream of bytes. FIG. 2 is an example of a rotated frame 100 received by the receiver, wherein the audio channel 30 and video channel 40 are rotated with respect to frame 10 in FIG. 1. Also, note that the service channel 50 is located in between the audio and video channels in frame 100. The receiver then uses the service channel 50 to reorient frame 100 in order to reconstruct frame structure 10. However, the receiver needs to first determine in which subchannel of frame 100 is the service channel 50 located.
In order to locate the service channel 50 in frame 100, an algorithm is typically used which separates and collates by bit position each byte in the stream of bytes received. The algorithm needs to collate the bits in each subchannel in a separate bit-group, and then compare each bit-group against the predesignated bit-pattern. A typical programming routine written in C-language, for collating bits in such manner, is shown in FIG. 3. The programming routine of FIG. 3 will be discussed in conjunction with the drawing of FIG. 4.
FIG. 4 shows a source of n bytes to be collated. FIG. 4 can for example depict the case wherein a series of n bytes forming one or more frame structures, similar to that shown in FIG. 1, are consecutively received and are stacked in the order received. Each byte is shown to consist of 8 bits, wherein the eight bit positions in each byte are designated as bit position 0 through bit position 7 starting with the least significant bit position. The stack of n bytes in FIG. 4 forms 8 bit-columns (subchannels), in one of which the predesignated bit-pattern is located. Hereinafter, each of the eight bit-columns in FIG. 4 will be referred to as a subchannel corresponding to one of the eight bit positions 0-7.
The program routine of FIG. 3 makes use of: i) an 8-bit "Byte" register in which a byte retrieved from the source of bytes in FIG. 4 is held; ii) an 8-bit "Bit" register used to prepare a bit for collation; and iii) eight "Accum" registers, in each of which one of the eight subchannels is collated. The length of each Accum register is dictated by the number of bits in the bit-pattern being sought, i.e., if the bit-pattern being sought is 10 bits in length, each of the eight Accum registers would need to be at least 10 bits in length.
The program code lines 1-31 in FIG. 3 collate eight bits of a byte retrieved from the source of bytes in FIG. 4. Therefore, if for example a total of 10 bytes were to be collated, code lines 1-31 need to be repeated 10 times, once for each byte.
Code line 1 of the program in FIG. 3 retrieves the next byte to be collated from the source of bytes in FIG. 4, placing that byte in the Byte register. Each of the subsequent group of programming code lines 2-4, 5-8, 9-12, . . . , 25-28, and 29-31 collate one bit position of the byte retrieved, starting with the least significant bit position (LSB) and ending with the most significant bit position (MSB), respectively.
Code lines 2-4 collate the least significant bit position (bit position 0) of the Byte register into the Accum register 0. Code line 2 performs a masking step wherein all the bit positions of the Byte register, other than bit position 0, are cleared. This masking operation is carried out by logically and non-destructively ANDing the contents of the Byte register with the binary value 00000001. The result is then placed in the Bit register.
Code line 3 shifts the contents of the Accum register 0 by 1 bit position to the left, thereby opening up the least significant bit position of the Accum register 0. Also, this shift operation preserves the previously collated bits if any.
Code line 4 places the bit value in the bit position 0 of the byte retrieved in the least significant bit position of the Accum register 0. This operation is carried out by logically ORing the contents of the Accum register 0 with that of the Bit register.
Code lines 5-8 collate bit position 1 of the Byte register into the Accum register 1 in a similar manner to the collation routine of code lines 2-4. However, collation of bit position 1 requires an additional shift operation in comparison with the collation routine of code lines 2-4. Since the masking operation clears all but the least significant bit position of the Bit register, it is necessary to shift the bit to be collated to the least significant bit position of the Byte register prior to placing the contents of the Byte register in the Bit register. This shift operation, shown in code line 5 of FIG. 3, is non-destructive, i.e., in collating bit position 2, the bit value in bit position 2 needs to be shifted two bit positions to the right. Upon completion of the operation of code line 4, bit position 1 of the retrieved byte is collated into the Accum register 1.
All subsequent collation routines are similar to the collation routine of code lines 5-8, except for the collation of the most significant bit position (bit position 7). The collation routine of code lines 29-31 collate bit position 7. As apparent from code lines 29-31, no masking operation is required in collating this bit position because, shifting the bit value in bit position 7 seven bit positions to the right, clears all bit positions other than the least significant bit position (the shifted bit position 7).
Therefore, upon completion of the operation in code line 31, each of the 8 bits in the retrieved byte are collated in one of the eight Accum registers. Repeating code lines 1-31 the requisite number of times will result in collation of the bits in each of the subchannels in FIG. 4 in one of the eight Accum registers, i.e., each of the eight subchannels corresponding to one of the eight bit positions 0-7 in FIG. 4, would be accumulated in the corresponding one of the eight Accum registers 0-7.
A "compare" operation, not shown in FIG. 3, may be carried out after collation of either one byte or a number of bytes. The comparison operation performed after collation of one byte, helps determine whether the bits in the byte collated are part of the predesignated bit-pattern; or alternatively after collation of the requisite number of bytes, the compare operation helps determine which of the 8 Accum registers, if any, contain the predesignated bit-pattern.
Each program code line in FIG. 3 requires one clock cycle to carry out the corresponding operation. Accordingly, a total of 31 clock cycles are required to complete the collation of one byte. As mentioned earlier, the number of times that steps 1-31 need to be repeated depends on the length of the predesignated bit-pattern, i.e., if the predesignated bit-pattern is 10 bits long, the collation routine of steps 1-31 need to be repeated 10 times, thereby requiring a total of 310 clock cycles. As can be seen, as the number of bytes to be collated increases, the number of clock cycles required increase dramatically. Therefore, the collation time can become prohibitive.